// 双指针秒杀七道链表题目
// NB: 链表题属于那种 难者不会, 会者不难! 
//
// 题一: 合并两个有序链表 - 简单题
// 思路: 定义一个虚拟头结点(哨兵位头结点)
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        ListNode* newnode = new ListNode(-1);
        ListNode* p = newnode;

        ListNode* p1 = list1, *p2 = list2;
        while(p1 && p2)
        {
            if(p1->val < p2->val)
            {
                p->next = p1;
                p1 = p1->next;
            }
            else
            {
                p->next = p2;
                p2 = p2->next;
            }
            p = p->next;
        }
        if(p1)
            p->next = p1;
        if(p2)
            p->next = p2;

        return newnode->next;
    }
};


// 题二: 分隔链表 - 中等难度题
// 思路:
// 1. 定义两个虚拟头结点
// 2. 将原链表分成两个小链表, 一段是比x小的, 一段是不小于x的
class Solution {
public:
    ListNode* partition(ListNode* head, int x) {
        ListNode* newnode1 = new ListNode(-1), *p1 = newnode1;
        ListNode* newnode2 = new ListNode(-1), *p2 = newnode2;
        ListNode* p = head;

        while(p)
        {
            if(p->val < x)
            {
                p1->next = p;
                p1 = p1->next;
            }
            else
            {
                p2->next = p;
                p2 = p2->next;
            }
            p = p->next;
        }
        p2->next = nullptr;
        p1->next = newnode2->next;

        return newnode1->next;
    }
};


// 题三: 合并K个升序链表 - 困难题
// 思路:
// 1. 定义一个最小堆, 将K个链表的头结点插入其中, 此时堆顶数据是最小的
// 2. 定义一个虚拟头结点, 取出堆顶数据尾插到其后, 注意边界问题 - 链表中一般都是头结点是否为空(即链表是否为空)
class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) 
    {
        if(lists.empty())
            return nullptr;

        // 定义一个虚拟头结点
        ListNode* newnode = new ListNode(-1), *p = newnode;

        // 定义一个最小堆
        priority_queue<ListNode*, vector<ListNode*>, function<bool(ListNode*, ListNode*)>> pq([] (ListNode* a, ListNode* b) {return a->val > b->val;} );


        // 将K个链表的头结点插入到最小堆中
        for(auto head : lists)
        {
            if(head)
                pq.push(head);
        }

        while(!pq.empty())
        {
            // 获取最小节点
            ListNode* next = pq.top();
            p->next = next;
            pq.pop();

            // 将最小节点的下一个节点插入到最小堆中
            if(next->next)
                pq.push(next->next);

            p = p->next;
        }
        
        return newnode->next;
    }
};


// 题四: 单链表的倒数第K个节点 - 简单题
// 思路:
// 本题比较巧妙, 定义两个指针, p1先走K步, 然后p2从头开始和p1一起走.
// 当p1指向空时, p2所在的位置就是第K个节点
class Solution {
public:
    
    ListNode* FindKthToTail(ListNode* pHead, int k) {
    
        // write code here
        ListNode* p1 = pHead, *p2 = p1;

        // p1先走k步
        for(int i = 0; i < k; i++)
        {
            // 注意判断防止越界导致段错误
            if(p1)
                p1 = p1->next;
            else
                return nullptr;
        }

        // p1和p2同时走n-k步, 此时p1指向nullptr, p2所在位置即答案
        while(p1)
        {
            p1 = p1->next;
            p2 = p2->next;
        }
        
        // 此时p2指向n-k+1个节点
        return p2;
    }
};



// 题四变形: 删除链表的倒数第N个节点
// 思路:
// 1. 单链表中删除某一个节点, 前提是要找到该节点的前一个节点
// 2. 定义虚拟头结点, 将head尾插其后, 防止头删第一个节点
// 3. 注意单链表中对于虚拟头结点的使用
//
//
// 补充: 单链表中何时需要定义虚拟头结点
// 当你需要创造一条新链表的时候，可以使用虚拟头结点简化边界情况的处理。
// 比如说，让你把两条有序链表合并成一条新的有序链表，是不是要创造一条新链表？
// 再比如你想把一条链表分解成两条链表，是不是也在创造新链表？这些情况都可以使用虚拟头结点简化边界情况的处理。
//
//
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) 
    {
        // 定义一个虚拟头结点 - 注意单链表对虚拟头结点的运用
        ListNode* newnode = new ListNode(-1);
        newnode->next = head; // 这样一来即使删头结点也没关系

        // 单链表中删除某一个节点, 前提需要找到它前一个节点
        ListNode* prev = findFromEnd(newnode, n + 1);
        
        prev->next = prev->next->next;

        return newnode->next;
    }

    // 单链表中找倒数第K个节点
    ListNode* findFromEnd(ListNode* head, int k)
    {
        // 定义两个指针p1和p2, p1先走k步(再走n-k步到尾), 然后p2从头开始h和p1一起走
        // 直到p1指向空, 此时p2在第n-k+1个节点的位置, 即倒数第k个节点
        ListNode* p1 = head, *p2 = head;

        if(head == nullptr)
            return nullptr;

        for(int i = 0; i < k; i++)
        {
            if(p1)
                p1 = p1->next;
            else
                return nullptr;
        }

        while(p1)
        {
            p1 = p1->next;
            p2 = p2->next;
        }

        return p2;
    }
};


// 题五: 链表的中点 - 简单题
// 思路: 快慢指针
class Solution {
public:
    ListNode* middleNode(ListNode* head) 
    {
        // 定义快慢指针
        ListNode* slow = head;
        ListNode* fast = head;

        // 快指针一次走两步, 慢指针一次走一步
        // 当快指针指向末尾时, 慢指针即是中点
        // 画图更好理解
        while(fast && fast->next)
        {
            slow = slow->next;
            fast = fast->next->next;
        }

        return slow;
    }
};


// 题六: 判断链表是否有环
// 思路: 快慢指针
//
class Solution {
public:
    bool hasCycle(ListNode *head) 
    {
        // 定义快慢指针
        ListNode* slow = head;
        ListNode* fast = head;

        while(fast && fast->next)
        {
            slow = slow->next;
            fast = fast->next->next;

            if(slow == fast)
            {
                return true;
            }
        }  

        return false;  
    }
};



// 题七: 环形链表II
// 思路: 根据博客: https://bit-runout.blog.csdn.net/article/details/121843258
class Solution {
public:
    ListNode *detectCycle(ListNode *head) 
    {
        // 定义快慢指针
        ListNode* slow = head;
        ListNode* fast = head;

        // 判断链表是否有环
        while(fast && fast->next)
        {
            slow = slow->next;
            fast = fast->next->next;

            if(slow == fast)
                break;
        }    

        // 循环非break退出(不满足循环条件退出时), 说明没环
        if(fast == nullptr || fast->next == nullptr)
            return nullptr;

        // 否则有环, slow从头重新开始走
        // 二者再次相遇即为入口点
        slow = head;
        while(slow != fast)
        {
            slow = slow->next;
            fast = fast->next;
        }

        return slow;
    }
};


// 题八: 相交链表 - 简单题
// 思路: 很巧, 最好画图去理解
// 1. 定义两个指针, p1指向链表A, p2指向链表B
// 2. p1遍历完链表A然后遍历链表B, p2遍历完链表B然后遍历链表A
// 这样做是为了让它们长度相同, 这样即可得到交点, 哪怕没有交点也可得到nullptr
class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) 
    {
        // 定义两个指针, p1指向链表A, p2指向链表B
        ListNode* p1 = headA;
        ListNode* p2 = headB;

        // 为了让p1和p2遍历链表的长度一样, 采用下面的做法
        while(p1 != p2)
        {
            // p1遍历完链表A, 开始遍历链表B
            if(p1 == nullptr)
                p1 = headB;
            else
                p1 = p1->next;

            // p2遍历完链表B, 开始遍历链表A
            if(p2 == nullptr)
                p2 = headA;
            else
                p2 = p2->next;
        }

        // 交点返回即可 - 画图去理解
        return p1;
    }
};


